package _02_动态数组;

import _01_第一季._00_公共接口.AbstractList;

/*
    动态数组
 */
@SuppressWarnings("unchecked")
public class ArrayList<E> extends AbstractList<E>{
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    public ArrayList(){
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity){
        capacity = Math.max(capacity,DEFAULT_CAPACITY);
        elements = (E[]) new Object[capacity];
        size = 0;
    }

    // 在指定索引处添加元素
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacity(size + 1);

        for(int i=size;i>index;--i){
            elements[i] = elements[i-1];
        }
        elements[index] = element;
        size++;
    }

    //扩容方法
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if(capacity <= oldCapacity) return;

        //扩容原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];

        for(int i=0;i<size;++i){
            newElements[i] = elements[i];
        }

        elements = newElements;

        System.out.println(oldCapacity+"扩容为:"+newCapacity);
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

    @Override
    public E set(int index, E element) {
        rangeCheck(index);
        E ret = elements[index];
        elements[index] = element;
        return ret;
    }

    @Override
    public void remove(E element) {
        int index = indexOf(element);
        if(index!=ELEMENT_NOT_FOUND){
            remove(index);
        }else{
            throw new ArrayIndexOutOfBoundsException("元素不存在");
        }
    }

    // 删除元素在指定索引
    @Override
    public E remove(int index) {
        rangeCheck(index);

        E ret = elements[index];
        for(int i=index+1;i<size;++i){
            elements[i-1] = elements[i];
        }
        elements[--size] = null;

        trim();
        return ret;
    }

    //缩容方法
    private void trim() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1;
        if(size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY ) return;

        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0;i<size;++i){
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(oldCapacity + "缩容为:"+newCapacity);
    }

    @Override
    public int indexOf(E element) {
        for(int i=0;i<size;++i){
            if(valEquals(element,elements[i])) return i;
        }
        return ELEMENT_NOT_FOUND;
    }

    private boolean valEquals(Object v1,Object v2){
        return (v1 == v2) || (v1 != null && v1.equals(v2));
    }

    @Override
    public void clear() {
        for(int i=0;i<size;++i){
            elements[i] = null;
        }

        size = 0;

        if(elements!=null && elements.length >DEFAULT_CAPACITY){
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(String.format("ArrayList:%d/%d[",size,elements.length));
        if(isEmpty()){
            sb.append("]");
        }else{
            for(int i=0;i<size;++i){
                sb.append(elements[i]);
                if(i!=size-1){
                    sb.append(",");
                }else {
                    sb.append("]");
                }
            }
        }
        return sb.toString();
    }
}
